package 题目集.单调栈or队列.单调栈.保留可能性;

import org.junit.Test;

/**
 * 给定一个整数数组 A，坡是元组 (i, j)，其中  i < j 且 A[i] <= A[j]。这样的坡的宽度为 j - i。
 * 找出 A 中的坡的最大宽度，如果不存在，返回 0 。
 * https://leetcode.cn/problems/maximum-width-ramp/description/
 */
public class 最大宽度坡 {
    /**
     * 暴力解：
     *      枚举每个起点，找到该起点最右侧比它大的位置，然后计算最大宽度
     *      时间复杂度：O(n^2)
     * 单调栈解：
     *      假如当前数比之前的数要大，那么当前数作为起点的宽度一定比之前的要小，即没有必要保留当前数。
     *      如果当前数比之前的数要小，那么当前数作为起点的宽度有可能比之前的要大，也有可能要小，所以需要保留当前数和之前的数。
     *      用单调栈保留这些可能性之后，从后往前遍历，找到最大宽度
     */
    public int maxWidthRamp(int[] nums) {
        int[] stack = new int[nums.length];
        int top = 0;    //预先添加 第一个
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] < nums[stack[top]]) {
                stack[++top] = i;
            }
        }
        int max = 0;
        for (int i = nums.length - 1; i >= 0; i--) {
            while (top >= 0&&nums[stack[top]] <= nums[i]) {
                max = Math.max(max, i - stack[top]);
                top--;
            }
        }
        return max;
    }

    @Test
    public void test() {
        System.out.println(maxWidthRamp(new int[]{1, 0}));
    }
}
